/*
 * @Author: szx
 * @Date: 2022-01-06 13:52:17
 * @LastEditTime: 2022-01-21 14:07:32
 * @Description:
 * @FilePath: \leetcode\700-799\714\714.js
 */
/**
 * @param {number[]} prices
 * @param {number} fee
 * @return {number}
 */
var maxProfit = function (prices, fee) {
    let res = 0;
    let minPrice = prices[0];
    for (let i = 1; i < prices.length; i++) {
        // 如果当前价格低于最低的价格，就购买
        if (prices[i] < minPrice) minPrice = prices[i];
        // 如果价格在最低价格和手续费之间，那么就不卖
        if (prices[i] >= minPrice && prices[i] <= minPrice + fee) {
            continue;
        }
        // 如果高于手续费+最低价格，那么就可以卖了
        // 可能有多次利润计算，但是每次最低价格都减去了手续费，这样子最后一次收的时候只有一次手续费
        if (prices[i] > minPrice + fee) {
            res += prices[i] - minPrice - fee;
            minPrice = prices[i] - fee;
        }
    }
    return res;
};

var maxProfit = function (prices, fee) {
    // dp[i][0]表示持有股票拥有的现金，dp[i][1]表示不持有股票拥有的现金
    const n = prices.length;
    const dp = new Array(n).fill(0).map(() => new Array(2).fill(0));
    dp[0][0] = -prices[0];
    for (let i = 1; i < n; i++) {
        dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] - prices[i]);
        dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] + prices[i] - fee);
    }
    return Math.max(dp[n - 1][0], dp[n - 1][1]);
};
console.log(maxProfit([1, 3, 2, 8, 4, 9], 2));
